#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFF_SIZE 256

int verbose = 0;

// Questa struct e' utilizzata per memorizzare alcuni dati di interesse delle sottostrutture
typedef struct Subs {
	unsigned int inst;  	// numero di istanze
	unsigned int norm;  	// norma
	char orphan;        	// indica se la sottostrutttura e' figlia di altre sottostrutture (orphan == 0) o meno (orphan == 1)
	unsigned int nsons;		// numero di figli
	float diversity;		// valore della diversità per la sottostruttura corrente se gia' calcolatolo, altrimenti -1
	struct Childs * son;	// puntatore alla lista di figli
}Subs;

// Questa struct e' utilizzata per realizzare una lista di figli di una data sottostruttura
typedef struct Childs{
	struct Subs * me;
	struct Childs * brother;
}Childs;

// Questa funzione calcola la diversita' tra le sottostrutture di un grafo create da subdue
void diversity(char* subs, char* exp_path, char *subdue_binpath);

// Questa funzione calcola il numero trasformazioni unitarie necessarie a trasformare il grafo 1 nel grafo 2
int distance(char *filename_1, char *filename_2, char *subdue_binpath);

// Questa funzione calcola il contributo sulla diversita' di un cluster a partire da un array di
// sottostrutture e richiama se stessa per ognuno dei figli di cluster
float diverrecursive(Subs *root, Subs *cluster, Subs *myfather, char *exp_path, char *subdue_binpath);

// Questo programma necessita dei seguenti parametri:
// - "-v" (opzionale) per abilitare la modalita' verbose
// - il file .subs (obbligatorio)
int main ( int argc, char* argv[] )
{
	// Viene salvato il tempo di calendario all'inizio dell'esecuzioneone per poterne calcolare la durata
	time_t inizio = time(NULL);

	// Queste sono le variabili che conterranno i percorsi dei files dati in input
	char file_subs[BUFF_SIZE], exp_path[BUFF_SIZE], subdue_binpath[BUFF_SIZE], create_dir[BUFF_SIZE];

	// Se viene passato il parametro "-v" viene attivata la modalita' verbose
	// altrimenti viene stampato l'help
	if (argc == 3 && !strcmp(argv[1],"-v"))
		verbose=1;
	else if(argc != 2)
	{
		fprintf(stderr, "Usage: %s [-v] <file.subs>", argv[0]);
		exit(EXIT_FAILURE);
	}

	// Vengono settati i percorsi agendo sulle stringhe
	strcpy(file_subs, argv[verbose+1]);
	strcpy(exp_path, argv[verbose+1]);
	char *lastslash = strrchr(exp_path, '/');
	if (lastslash)
		exp_path[(int)(lastslash - exp_path)] = '\0';
	else
	{
		strcpy(exp_path, ".");
		sprintf(file_subs, "./%s", argv[verbose+1]);
	}

	// Vengono create (se non esistono) le cartelle per contenere i log ed i files temporanei
	sprintf(create_dir, "mkdir -p %s/{temp,log}", exp_path);
	system(create_dir);
	sprintf(exp_path, "%s/temp", exp_path);

	strcpy(subdue_binpath, argv[0]);
	lastslash = strrchr(subdue_binpath, '/');
	if (lastslash)
		subdue_binpath[(int)(lastslash - subdue_binpath)] = '\0';
	else
		strcpy(subdue_binpath, ".");

	// La diversita' viene effettivamente lanciata coi parametri trovati
	diversity(file_subs, exp_path, subdue_binpath);

	// Viene salvato il tempo di calendario alla fine dell'esecuzione
	time_t fine = time(NULL);

	// Viene scritta la durata dell'esecuzione
	printf("\nIl calcolo della diversita' ha richiesto circa %d secondi\n", (int)difftime(fine, inizio));

	return 0;
}

// Questa funzione calcola il numero trasformazioni unitarie
// necessarie a trasformare il grafo 1 nel grafo 2
int distance(char *filename_1, char *filename_2, char *subdue_binpath)
{
	// Valore di default, se viene ritornato indica un errore
	int distance = -1;

	// Comando da eseguire nella shell di sistema
	// Richiama il tool GM di subdue che calcola la distanza tra due grafi
	// e ne scansiona l'output alla ricerca dell'informazionereindirizzandola
	// sul file aperto dalla "popen()"
	char gm_string[BUFF_SIZE];
	sprintf(gm_string, "%s/gm %s %s | grep Match | cut -d \" \" -f4", subdue_binpath, filename_1, filename_2);

	// Viene aperto, letto e convertito il file contenente il valore della distanza
	FILE *file_dist = (FILE *)popen( gm_string, "r" );
	char buffer[BUFF_SIZE];
	if (file_dist == NULL)
	{
		if(verbose) printf("\nErrore nella creazione della \"pipe\"\n");
	}
	else
	{
		fgets(buffer, sizeof(buffer), file_dist);
		pclose(file_dist);
		distance = atoi(buffer);
	}

	// Stampato e ritornato il valore della distanza tra i 2 grafi in input
	if(verbose) printf("\nLa distanza tra %s e %s e' %d\n\n", strrchr(filename_1, '/')+1, strrchr(filename_2,'/')+1, distance);
	return distance;
}

// Questa funzione calcola la diversita' tra le sottostrutture di un grafo create da subdue
void diversity(char* filename_subs, char* exp_path, char *subdue_binpath)
{
	// Il file .subs viene aperto e letto riga per riga
	FILE* file_subs = fopen(filename_subs, "r");
	if (file_subs == NULL)
	{
		if(verbose) printf("Il file %s non esiste\n", filename_subs);
	}
	else
	{
		if(verbose) printf("Il file %s e' stato caricato\n", strrchr(filename_subs,'/')+1);
	}

	char buffer[BUFF_SIZE];
	unsigned long int nsubs = 0;
	char filename_g[BUFF_SIZE];
	FILE* file_g = NULL;

	// Questo ciclo permette di contare il numero di sottostrutture
	// inserite da subdue nel file .subs
	// Contestualmente vengono creati i files SUB_x.g contenenti
	// i grafi relativi ad ogni sottostruttura
	while (fgets(buffer, sizeof(buffer), file_subs))
	{
		// Il file e' diviso in sezioni corrispondenti alle varie sottostrutture
		// La prima riga di ognuna e' una stringa del tipo "SUB_x"
		// dove "x" e' il numero progressivo della struttura
		if (buffer[0] == 'S')
		{
			// Viene creato il file SUB_x.g per contenere la sottostruttura
			if (file_g)
				fclose(file_g);
			sprintf(filename_g, "%s/SUB_%lu.g", exp_path, ++nsubs);
			file_g = fopen(filename_g, "w+");
		}
		// Vengono scritte le righe della sottostruttura nell'ultimo file aperto
		else if (buffer[0] != '\n')
			fputs(buffer, file_g);
	}
	if (file_g)
		fclose(file_g);

	// Viene creato un array di struct, viene aggiunto 1 per considerare anche la "root"
	// L'utilita'� di questa sottostruttura fittizia (SUB_[0]) verra'� spiegata in seguito
	Subs SUB_[nsubs+1];
	unsigned long int i;
	// Inizializzazione a zero delle sottostrutture
	for (i =0; i<= nsubs; i++)
	{
		SUB_[i].norm = 0;
		SUB_[i].inst = 1;
		SUB_[i].orphan = 1;
		SUB_[i].nsons = 0;
		SUB_[i].son = NULL;
		SUB_[i].diversity = -1;
	}

	// Vengono aperti in sequenza i files .g appena creati
	unsigned long int current_sub = 0;
	while (nsubs - current_sub++)
	{
		sprintf(filename_g, "%s/SUB_%lu.g", exp_path, current_sub);
		file_g = fopen(filename_g, "r");
		if (file_g == NULL)
		{
			if(verbose) printf("Il file %s non esiste\n", filename_g);
		}
		else
		{
			if(verbose) printf("Il file %s e' stato caricato\n", strrchr(filename_g, '/')-4);
		}
		// Viene letto il file riga per riga
		while (fgets(buffer, sizeof(buffer), file_g))
		{
			// Ad ogni riga letta viene incrementata la norma
			// della sottostruttura legata al file corrente
			SUB_[current_sub].norm++;

			// Se viene rilevata la sottostring "SUB_x" significa che la sottostruttura corrente
			// e' figlia della sottostruttura "x"
			int z=0;
			while (buffer[z] && buffer[z] != 'S')
				z++;
			if (buffer[z] == 'S' && buffer[z+1] == 'U' && buffer[z+2] == 'B' && buffer[z+3] == '_')
			{
				int father = (int)strtol(&buffer[z+4], NULL, 10);
				// Viene incrementato il numero di istanze della sottostruttura padre "x"
				SUB_[father].inst++;
				// La sottostruttura corrente ha almeno un padre: non e' piu' orfana
				SUB_[current_sub].orphan = 0;
				// La sottostruttura corrente viene inserita nella lista dei figli della sottostruttura padre "x"
				// solo se non era gia' in testa alla lista (non potrebbe trovarsi altrove)
				if (SUB_[father].son == NULL || SUB_[father].son->me != &SUB_[current_sub])
				{
					Childs * orphan = SUB_[father].son;
					SUB_[father].son = (Childs *)malloc(sizeof(Childs));
					SUB_[father].son->brother  = orphan;
					// Viene legato alla struttura di tipo child il corrispondente
					// elemento dell'array di sottostrutture
					SUB_[father].son->me = &SUB_[current_sub];
					// Incrementato il numero di figli della sottostruttura padre "x"
					SUB_[father].nsons++;
				}
			}
		}
	}

	// Tutte le sottostrutture orfane (ovvero quelle di primo livello)
	// vengono assegnate d'ufficio come figlie della sottostruttura fittizia "root" (SUB_[0])
	for (i=1; i <= nsubs; i++)
	{
		if (SUB_[i].orphan)
		{
			Childs * temp = SUB_[0].son;
			SUB_[0].son =  (Childs *)malloc(sizeof(Childs));
			SUB_[0].son->brother = temp;
			SUB_[0].son->me = &SUB_[i];
			SUB_[0].nsons++;
		}
	}

	// Viene stampata a fini di controllo l'elenco delle sottostrutture
	// con i relativi dati e la lista degli eventuali figli
	if (verbose)
		for (i = 0; i<=nsubs; i++)
		{
			printf("\nSUB_%lu.norm = %d\n", i, SUB_[i].norm);
			printf("SUB_%lu.inst = %d\n", i, SUB_[i].inst);
			printf("SUB_%lu.orphan = %d\n", i, SUB_[i].orphan);
			printf("SUB_%lu.nsons = %d\n", i, SUB_[i].nsons);
			Childs * temp = SUB_[i].son;
			while (temp)
			{
				printf("\tSUB_%lu.son->me %d\n", i,  (int)(temp->me - SUB_));
				temp = temp->brother;
			}
		}

	// Viene ritornato il valore calcolato dalla funzione ricorsiva per il calcolo
	// effettivo della diversita' a partire dalla sottostruttura "root"
	float total_dive = diverrecursive(SUB_, &SUB_[0], NULL, exp_path, subdue_binpath);

	printf("\nLa diversita' vale: %3.3f\n\n", total_dive);
}

// Questa funzione calcola il contributo sulla diversita' di un cluster
// a partire da un array di sottostrutture e richiama se stessa per ognuno dei figli di cluster
float diverrecursive(Subs *root, Subs *cluster, Subs *myfather, char* exp_path, char *subdue_binpath){

	// Questa variabile e' l'accumulatore dei contributi di diversita'
	// tra le varie istanze di questa funzione
	static float dive;

	// Vengono confrontati tutti i figli della sottostruttura corrente
	int i, j;
	float num = 0, den = 0;

	// Se il cluster corrente ha figli ...
	if (cluster->nsons > 1 )
	{
		// ... e se non e' stata gia' calcolata ...
		if (cluster->diversity == -1)
		{
			// ... viene calcolata la diversita'
			for(i=0; i < cluster->nsons-1; i++)
				for(j=i+1; j < cluster->nsons; j++)
				{
					Childs * son_i = cluster->son;
					Childs * son_j = cluster->son;
					int ii = i, jj = j;
					while (ii--)
						son_i = son_i->brother;
					while (jj--)
						son_j = son_j->brother;
					char file_i[BUFF_SIZE];

					// L'indirizzo dell'array viene passato per permettere (tramite aritmetica
					// dei puntatori) di individuare l'indice corretto dell'elemento dell'array corrente
					sprintf(file_i, "%s/SUB_%d.g", exp_path, (int)(son_i->me - root));
					char file_j[BUFF_SIZE];
					sprintf(file_j, "%s/SUB_%d.g", exp_path, (int)(son_j->me - root));
					float distanza = distance(file_i, file_j, subdue_binpath);

					// Nel numeratore vengono sommati tutti i contributi di distanza tra i vari figli
					// fratto la maggiore delle norme dei figli
					num += son_i->me->inst*son_j->me->inst*distanza/((son_i->me->norm > son_j->me->norm)?son_i->me->norm:son_j->me->norm);
					if(verbose) printf("Numeratore = %f\n", num);

					// Nel denominatore vengono sommati i prodotti delle norme dei 2 figli
					// di volta in volta in esame
					den += son_i->me->inst * son_j->me->inst;
					if(verbose) printf("Denominatore = %f\n", den);
				}
			// Viene sommato alla variabile statica il contributo di diversita' della sottostruttura corrente
			// e salvato in un campo della stessa per non doverlo ricalcolare in futuro
			cluster->diversity = num/((den)?den:1);
		}
		if (myfather)
			myfather->diversity += cluster->diversity;
		dive += cluster->diversity;
	}

	// Viene richiamata la funzione ricorsiva sui figli della sottostruttura corrente
	Childs * current_son = cluster->son;
	int z;
	for (z = 0; z < cluster->nsons; z++)
	{
		diverrecursive(root, current_son->me, cluster, exp_path, subdue_binpath);
		current_son = current_son->brother;
	}

	// Viene ritornato il valore della diversita'
	return dive;
}
